package com.heap.max;

import com.company.Array;

/**
 * 使用动态数组实现堆
 * （注意：堆本事还是一棵完全二叉树）
 * @param <E>
 */
public class MaxHeap<E extends Comparable<E>> {

    private Array<E> data;

    public MaxHeap(int capacity) {
        data = new Array<>(capacity);
    }
    public MaxHeap() {
        data = new Array<>();
    }

    /**
     * 使用heapify 构建一个完全二叉树，堆
     * 从第一个非叶子节点开始下沉
     * @param arr
     */
    public MaxHeap(E[] arr) {
        data = new Array<>(arr);
        for (int i = parent(arr.length - 1); i >= 0 ; i--) {
            siftDown(i);
        }
    }

    public int size() {
        return data.getSize();
    }
    public boolean isEmpty() {
        return data.isEmpty();
    }

    /**
     * 返回完全二叉树的数组表示中，一个索引表示的元素的父节点的索引
     * @param index
     * @return
     */
    private int parent(int index) {
        if (index == 0) {
            throw new IllegalArgumentException("index-0 doesn't have a parent node!");
        }
        return (index -1) / 2;
    }

    /**
     * 返回完全二叉树的数组表示中，一个索引表示的元素的左孩子的索引
     * @param index
     * @return
     */
    private int leftChild(int index) {
        return index * 2 + 1;
    }

    /**
     * 返回完全二叉树的数组表示中，一个索引表示的元素的右孩子的索引
     * @param index
     * @return
     */
    private int rightChild(int index) {
        return index * 2 + 2;
    }

    /**
     * 向堆中添加元素
     * @param e
     */
    public void add(E e) {
        data.addLast(e);
        // 需要上浮的索引就是最后添加的元素所以是getSize()-1
        siftUp(data.getSize() - 1);
    }

    /**
     * 堆中元素上浮
     * @param k
     */
    private void siftUp(int k) {

        // 必须是非根节点而且当前节点的父节点的索引要小于当前节点的索引
        while (k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0) {
            data.swap(k, parent(k));

            // 与父节点交换索引值然后进入下一轮循环
            k = parent(k);
        }
    }

    /**
     * 查看堆中最大的元素
     * @return
     */
    public E findMax() {
        if (data.getSize() == 0) {
            throw new IllegalArgumentException("Cannot find a max element from an empty heap!");
        }
        // 这里对是基于数组的实现的，第一个元素就是最大的值
        return data.get(0);
    }

    /**
     * 堆中的最大元素出队
     * @return
     */
    public E extractMax() {
        E ret = findMax();

        // 删除最大元素：将最大元素和最后一个元素调换位置，然后删除最后一个元素
        data.swap(0,data.getSize() - 1);
        data.removeLast();

        // 调整完全二叉树
        siftDown(0);

        return ret;
    }

    /**
     * 堆中节点下沉
     * @param k
     */
    private void siftDown(int k) {
        while (leftChild(k) < data.getSize()) {
            // 找到左右孩子中较大的节点
            int j = leftChild(k);

            /*
                此时data[j] 是左右子节点中最大的
                1. 因为如果j + 1 < data.getSize() 条件不满足，说明没有右节点，
                那j就是表示左节点，也是最大；
                2. 如果j + 1 < data.getSize()满足，说明有右节点
                但是 data.get(j + 1).compareTo(data.get(j)) > 0 不满足，
                说明右节点比左节点小，那还是左节点最大
                3. 如果条件满足，说明右边节点更大，于是将右边节点的索引赋值给j
                综上：经过在这个if条件之后，j表示的就是左右子节点中最大那一个
             */
            if (j + 1 < data.getSize() && data.get(j + 1).compareTo(data.get(j)) > 0) {
                j = rightChild(k);
            }
            // 如果当前节点大于左右节点就不需要调换位置
            if (data.get(k).compareTo(data.get(j)) >= 0) {
                break;
            }
            data.swap(k,j);

            // 这一步很重要：调换索引进入下一次循环
            k = j;
        }
    }

    /**
     * 堆的 replace 操作
     * 取出堆中的最大的元素并且替换成元素e
     * @param e
     * @return
     */
    public E replace(E e) {
        E ret = findMax();
        data.set(0, e);
        siftDown(0);
        return ret;
    }







}
